package com.watimer.algorithms.algorithms;

import java.util.*;

/**
 * @param
 * @author yan
 * @Description
 * @date 2019/12/20
 */
public class AlgorithmsTest {

    /**
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     */

    public static void main(String[] args){
        int[] nums = {3,2,4};
        int target = 6;
        twoSum(nums,target);
        twoSum2(nums,target);
    }

    // 第一次思路
    public static int[] twoSum(int[] nums, int target) {
        System.out.println("1"+ new Date());
        int[] re = {};
        List<Integer> aa = new ArrayList<Integer>();
        for(int i =0;i<nums.length;i++){
            for(int y = 0;y<nums.length;y++){
                if(i!=y){
                    int a = nums[i] + nums[y];
                    if(a==target){
                        aa = new ArrayList<>();
                        aa.add(i);
                        aa.add(y);
                        int[] res = {i,y};
                        return res;
                    }
                }

            }
        }
        return re;
    }

    // 优化版  暴力法
    public static int[] twoSum2(int[] nums, int target) {
        for(int i =0;i<nums.length;i++){
            for(int y = i+1;y<nums.length;y++){
                if((nums[i]+nums[y])==target){
                    return new int[] {i,y};
                }
            }
        }
        throw new IllegalArgumentException("无答案");
    }


    // 两遍哈希表
    public static int[] twoSum3(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    // 一遍哈希表
    public static int[] twoSum4(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
